/**
 * @author Galina Bulgakova
 * @author Peter Weirich
 *
 * Quellen: 
 * - 
 */

import java.util.Map;
import java.util.HashMap;
import java.util.Iterator;
import java.lang.Math;

public class ID3Algorithm {
	
	/** Konstruktor	*/
	 public ID3Algorithm(){}
	 
	 private String sOutput="Entscheidungsbaum:\n\n"; // Ausgabezeichenkette
	 
	 
	 /**
	 * @getDecisionTree: Die Funktion generiert anhand der Eingabedaten ein Entscheidungsbaum
	 * 		und gibt das Entscheidungsbaum als Zeichenkette aus.
	 * @param
	 *  	@paInput: Zwei dimensionales Array mit den Trainingsdaten, wobei der Array folgenderma�en aufgebaut ist:
	 * 					{{AttributName, AttributValue1,...,AttributValueN}}
	 * 		@paClassification: Array mit den Daten fuer die Klassifikation.
	 *                  Aufbau des Arrays: {ClassifikationName, ClassName1,...,ClassNameN}
	 *      @pClassEntropy: Entropy-Wert des Klassifikators.
	 *      			Achtung: beim 1. Aufruf der Funktion soll Default-Wert groesser 1 uebergeben werden!
	 * @return 
	 * 		@sOutput: Entscheidungsbaum als Zeichenkette
	 * 
	 * TODO Status: in Arbeit
	 */
	 public String getDecisionTree(final String[][] paInput, final String[] paClassification, double pClassEntropy){
                                                            // Koennte ein Fehler sein -1 abzuziehen
		 int setLength = (paClassification.length) - 1; //Laenge des Sets anhand des Klassifikator-Attributs ermitteln 
                 
                 if(setLength==0){
			 //TODO: Warnung ausgeben: Klassifikator-Attribut enthaelt keine Klassen
			 return "";
		 }
		 
		 int counter= paInput.length; //Die Anzahl von Attributen ermitteln
		 if(counter==0){
			 //Es gibt nichts zu berechnen
			 return sOutput+"/n Alle Daten sind bearbeitet.";
		 }
		 
		 if(pClassEntropy>1){ // Nur beim 1. Durchlauf die Klassifikator-Entropy berechnen
				 
			 //Entropy des Klassifikators aufgrund von paClassification berechnen
			 Map<String,Integer> mapClassification = this.getAttributsGain(paClassification);						 
			 pClassEntropy = this.getEntropy( setLength, mapClassification);
			 if (pClassEntropy==0){
				 //Alle Elemente aus paClassification gehoeren zu einer Klasse => ein Blatt erzeugen
				 //TODO: ein Blatt mit der Klasse als Bezeichner erzeugen
				 return sOutput;
			 }
		 }
		 
		 // Ein Attribut mit dem hoechsten Informatioswert waehlen:
		 
		 //Die Daten fuer die Erstellung des Baum-Knotens definieren und mit default-Werten initialisieren:
		 double bestInfoGain = 0; // Informationsgehalt des besten Attributs. Kleinst moegliche Informationsgehalt-Wert als default zuweisen
		 String bestAttr=""; //Die Bezeichnung des besten Attributs (zuckunftiger Knoten-Name) mit dem Informationsgehalt @bestInfoGain
		 Map<String,Integer> bestAttrData = new HashMap<String,Integer>(); // Statistik-Daten des Attributs @bestAttr
		 
		 // TODO: Die Kontainern fuer die Rekursion und Datenausgabe anlegen
		 // ??? Enthaelt Attribut-Werte (des @bestAttr) mit dem Entropy-Wert Null (=>Endknoten) Aufbau: Map<Attributwert-Bezeichnung, zugehoerige Klasse>,...>		 
		 //Map<String, String> endValues; 
		 
		 
		//Ueber die 1. Dimension von @paInput laufen und jeweils die Entropy von Attributen (2.Dimension) bestimmen.
		 for(int i=0; i<counter; i++){
			 
			 double attrEntropy=0;
			//Statistik ueber die Attr-Werte erstellen: Map<ValueName=Statistics,...>
			 Map<String,Integer> mapAttrValuesStat = this.getAttributsGain(paInput[i]); 
			 
			 //Die gesamte Attribut-Entropy anhand von Attribut-Werten im Bezug auf die Klassifikator-Klassen ermitteln:
			 Iterator iterator = mapAttrValuesStat.entrySet().iterator();
			 while(iterator.hasNext()) {
				 Map.Entry mapSet = (Map.Entry)iterator.next();
				 String valueName = mapSet.getKey().toString(); //Die Bezeichnung des Attribut-Wertes
				 
				//Die Anzahl des Auftretens des Attribut-Wertes innerhalb der Attribut-Spalte
			     int attrStat = ((Number)mapSet.getValue()).intValue(); 
			     
			     double attrProb = ((double)attrStat)/setLength; //Wahrscheinlichkeit des Auftretens des Attribut-Wertes
			     
			     //Statistik der Klassifikator-Klassen fuer den aktuellen Attribut-Wert (@valueName) erstellen
			     //z.B. fuer den Attribut-Wert (@valueName) `Young` des Attribut `Age` fuer Klassifikators `Country`: Map<Austria=1,Elsewhere=1> 
			     Map<String,Integer> maValueStat = new HashMap<String,Integer>();
			     for(int n=1; n<=setLength; n++){
			    	 if( paInput[i][n].equals(valueName) ){
			    		 String className = paClassification[n]; //Bezeichnung der Klasse des Klassifikator-Attributs
			    		 
			    		 //Statistik-Set f�r @className aktualisieren:
			    		 if(maValueStat.isEmpty())
                                         { 
                                             maValueStat.put(className, 1);
                                         } 
					 else 
                                         {
                                             if (maValueStat.get(className)!=null)
                                             { 
						 int newCounter = maValueStat.get(className) + 1;
						 maValueStat.put(className, newCounter); 
                                             }
                                             else
                                             { 
                                                 maValueStat.put(className, 1); 
                                             }
                                         }//end else
			    	 } 
			     }
			   //Entropy des Attributs in Abh�ngigkeit von Klassifikation-Werten bestimmen
			     double attrValueEntropy = this.getEntropy( attrStat, maValueStat);
			     attrEntropy = attrEntropy + attrProb*attrValueEntropy;
			     
			     //TODO: Vorbereitung fuer die Unterteilung der Knoten: welche Daten braucht man f�r die Ausgabe?
			     
			 }  //end while
			 
			 double attrInfoGain = pClassEntropy - attrEntropy; //Informationsgehalt des Attributs ausrechnen
			 if(bestInfoGain <= attrInfoGain){ 
				 //Attribut mit dem hoechsten Informationsgehalt merken
				 bestAttr = paInput[i][0]; //Die Bezeichnung des bestes Attributs merken
				 bestInfoGain = attrInfoGain; //bestes Informationsgehalt-Wert aktualisieren
				 bestAttrData = mapAttrValuesStat; //Statistik-Daten des besten Attributs merken
			 }
			 
			
		 }// end for
		 
		 
		 //TODO: Ein Knoten des Entscheidungsbaums erstellen. Benutze @bestAttr, @bestInfoGain, @bestAttrData
		 //TODO: Rekursiver Aufruf der Funktion
		 
		 return sOutput;
	 }
	 
	 /**
	 * @getEntropy: Die Funktion ermittelt die Gewichte von Attribut-Werten 
	 * @param  paInput: Array mit den Attribut und Attribut-Werten
	 * @return mp: Gain-Wert
	 * Status: fertig
	 */
	 private Map<String,Integer> getAttributsGain(final String[] paInput){
		
		 int arrLength = paInput.length; // Laenge des Arrays ermitteln 
		 
		 Map<String,Integer> mp = new HashMap<String,Integer>();
		 
		 // Alle ermittelte Werte in @mp ablegen 
		 for(int i=1; i<arrLength; i++){
			 
			 String attrName = paInput[i];			 
			 if(mp.isEmpty()){ mp.put(attrName, 1);} 
			 else {
				 if (mp.get(attrName)!=null){ 
					//der Attributwert mit der Bezeichnung attrName ist bereits im @mp vorhanden,
					//also den Schluesselwert um Eins erhoehen
					 int newValue = mp.get(attrName) + 1;
					 mp.put(attrName, newValue); 
				 }
				 else{ mp.put(attrName, 1); }
			}//end else
		 }//end for
		 
		 return mp;
	 }
		 
	 /**
	 * @getEntropy: Die Funktion berechnet die gesamte Entropy von Elementen aus @pAttrMap
	 * @param  
	 * 		@pAttrMap: Map mit der Statistik der Eigenschaften. Aufbau von @pAttrmap: <Eigenschaft = Statistik des Auftretens des Eigenschafts>
	 * 		@pSetLength: Laenge des Eigenschaften-Sets
	 * @return entropy: Entropy-Wert
	 */
	 private double getEntropy( int pSetLength, Map<String,Integer> pAttrMap){
	
		 double entropy = 0;
		 if(pAttrMap.isEmpty()){
			 //TODO: Warnung ausgeben
		 }
		 
		 Iterator iterator = pAttrMap.entrySet().iterator(); //Map-Iterator
		 while(iterator.hasNext()) {
                     Map.Entry mapSet = (Map.Entry)iterator.next();
		     double value = ((Number)mapSet.getValue()).doubleValue(); //Anzahl des Auftretens des Anttribut-Eigenschafts
		     double p = value/pSetLength; //Wahrscheinlichkeit des Auftrettens des Attributs-Eigenschaft
		     entropy = entropy + p * (Math.log(p)/Math.log(2));
		 }
                 
                 System.out.println(entropy); //Eingefuegt fuer Testzwecke
                 
		 return entropy*(-1);
	 }

}
